package _022_1_29

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
	listNodeSize := len(lists)
	resultListHead := ListNode{
		Next: nil,
	}
	tail := &resultListHead
	minI := 0
	minVal := 0
	for listNodeSize > 1 {
		for i := 1; i < listNodeSize; i++ {
			if lists[i] == nil {
				lists = append(lists[:i], lists[i:]...)
				i--
				listNodeSize--
			}
		}

		if listNodeSize < 1 {
			break
		}

		minVal = lists[0].Val
		minI = 0
		for i := 1; i < listNodeSize; i++ {
			if lists[i].Val < minVal {
				minVal = lists[i].Val
				minI = i
			}
		}
		tail.Next = lists[minI]
		lists[minI] = lists[minI].Next
		tail = tail.Next
		tail.Next = nil
	}

	for lists[0] != nil {
		tail.Next = lists[0]
		lists[0] = lists[0].Next
		tail = tail.Next
		tail.Next = nil
	}

	return resultListHead.Next

}
